package leetCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * err
 * LCR 015. 找到字符串中所有字母异位词
 * https://leetcode.cn/problems/VabMRr/description/
 */
class Solution {
    public static void main(String[] args) {
        findAnagrams("cbaebabacd", "abc");
    }
    public static List<Integer> findAnagrams(String ss, String pp) {
        int lenS = ss.length();
        int lenP = pp.length();
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        Map<Character, Integer> mapS = new HashMap<>();
        Map<Character, Integer> mapP = new HashMap<>();
        List<Integer> list = new ArrayList<>();
        //让p字符串的字符入完哈希表里
        for(int i = 0; i < lenP; i++) {
            mapP.put(p[i], mapP.getOrDefault(p[i], 0) + 1);
        }
        for(int left = 0, right = 0; right < lenS; right++) {
            if (mapS.size() <= lenP) {
                //进窗口
                mapS.put(s[right], mapS.getOrDefault(s[right], 0) + 1);
            }
            //判断
            if((right - left + 1) > lenP) {
                //出窗口
                mapS.remove(s[left]);
                left++;
            }
            //更新结果
            boolean flag = true;
            for(int i = 0; i < lenP; i++) {
                if(mapS.get(p[i]) != mapP.get(p[i])){
                    flag = false;
                    break;
                }
            }
            if(flag) {
                list.add(left);
            }
        }
        return list;
    }
}